package code;

//题目链接：https://leetcode.cn/problems/profitable-schemes/
public class ProfitableSchemes {
	public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int mod = 1000000007;
        int m=profit.length;
        int[][][] dp=new int[m+1][n+1][minProfit+1];
        //初始化: i=0时，从0个工作中选，员工数<=j,利润>=k，的选择数
        //dp[0][0][0]=1
        for(int j=0;j<=n;j++){
            dp[0][j][0]=1;
        }
        for(int i=1;i<=m;i++){
            for(int j=0;j<=n;j++){
                for(int k=0;k<=minProfit;k++){
                    dp[i][j][k]=dp[i-1][j][k]%mod;
                    if(j-group[i-1]>=0){
                        dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])])%mod;
                    }
                }
            }
        }
        return dp[m][n][minProfit];
    }
}
